The present invention relates to a method of and an apparatus for identifying transmission lines, space acoustic coupling routes and other unknown systems.
The application of unknown system identification with an adaptive filter, echo cancelers, noise cancelers, hauling cancelers, adaptive equalizers and so forth are well known in the art. As an example of the prior art, an echo canceler will be described, which is inserted on the four-line side of a two-line/four-line converter for canceling the echo leaking from the transmitting circuit to the receiving circuit.
The echo canceler uses an adaptive filter, which has tap coefficients greater in number than the impulse response length of an echo path, and cancels echo leaking from the transmitting circuit to the receiving circuit on the four-line side of the two-line/four-line converter by generating a pseudo echo (or echo replica) corresponding to the transmitted signal. The tap coefficients of the adaptive filter are corrected by taking the correlation between an error signal, which is obtained by subtracting the echo replica from a mixed signal, which contains the echo and the received signal in a mixed fashion, and the transmitted signal. A typical coefficient correction algorithm of such adaptive filter is described in "LMS Algorithm", Proceedings of IEEE, Vol. 63, No. 12, 1975, pp. 1692-1716 (hereinafter referred to as "Literature 1"), and "Learning Identification Method; LIM", IEEE Transactions on Automatic Control", Vol. 12, No. 3, 1967, pp. 282-287 (hereinafter referred to as "Literature 2").
Where a fixed delay is present between the point on the four-line circuit, at which the echo canceler is inserted, and a certain point on the two-line/four-line circuit, the echo canceler should have taps which can sufficiently cover both the maximum estimated fixed delay and the significant part of the actual impulse response. Where the fixed delay is long, therefore, the taps are enormous in number and give rise to increase of the hardware and increase of the convergence time by mutual interference of coefficient.
To solve these problems, it has been proposed a method of adaptive tap coefficient location control of an adaptive filter such as to locate tap coefficients in the neighborhood of the significant part of the echo path impulse response, the position of which is estimated as described in "A Fast Adaptive FIR Filter Algorithm with Reduced Computation for Adaptive Tap-Position Control", Proceedings of International Workshop on Intelligent Signal Processing and Communication Systems, IEEE, 1993, pp. 20-25 (hereinafter referred to as "Literature 3"). In the method shown in "Literature 3", the converging time is reduced by estimating the approximate position of the significant part and locating the tap coefficients only in the neighborhood of the estimated position.
FIG. 4 is a block diagram showing the construction of the echo canceler proposed in "Literature 3". The adaptive filter shown in FIG. 4 has (N-1) delay elements 20.sub.1 to 20.sub.N-1 for delaying a transmission signal inputted from a transmission signal input terminal 1, and has a total of N taps including zero delay taps. To generate the tap coefficients of the adaptive filter, L (N&gt;L) coefficient generators 30.sub.1 to 30.sub.L are provided. More specifically, the adaptive filter shown in FIG. 4, unlike other prior art adaptive filters, has such number of tap coefficients as to be above to realize a substantial part excluding the fixed delay part, and generates the echo replica by adaptively locating the tap coefficients in the neighborhood of the substantial part. To generate the echo replica, a routing switch 7 is provided, which switches the connection between the outputs of the delay elements on one hand and the coefficient generators on the other hand. The route switch 7 is controlled by a tap controller 9, and its outputs are supplied as delayed signals to the corresponding coefficient generators 30.sub.1 to 30.sub.L and also corresponding multipliers 40.sub.2 to 40.sub.L. The multipliers 40.sub.1 to 40.sub.L multiply the tap coefficient values outputted by the coefficient generators 30.sub.1 to 30.sub.L by the respective delay signals from the routing switch 7, and supply the resulting products to an adder 8. The adder 8 adds together the product outputs of the multipliers 40.sub.1 to 40.sub.L and outputs the sum as the echo replica. The transmission signal inputted to the transmission signal input terminal 1 is sent out from a transmission signal output terminal 2 to a transmission line, and supplied by a two-line/four-line converter 3 thereon to the two-line side. However, due to impedance mismatch the transmission signal partly leaks as an echo to the receiving side. The echo that is inputted from a received signal input terminal 4 is supplied to a subtractor 5. The subtractor 5 subtracts the echo replica outputted from the adder 8 from the echo, and sends out the difference result to a received signal output terminal 6. The difference is also supplied as an error signal for coefficient update to the coefficient generators 30.sub.1 to 30.sub.L.
Assuming the LMS algorithm shown in "Literature 1" for the coefficient updating, the coefficient generator 30.sub.i (i being 1, 2, . . . , L) can have a construction as shown in FIG. 5. The delayed signal and error signal supplied to the coefficient generator 30.sub.i are multiplied by each other in a multiplier 31, and the product therefrom is multiplied by a step size output from a switch 78 in a multiplier 32. The output of the multiplier 32 represents a coefficient correction amount, and it is added in an adder 33 to a coefficient value stored in a memory 34 as the tap coefficient. The sum is fed back to the memory 34. When a coefficient clear signal is inputted from a coefficient clear circuit 77 to it, the memory 34 forcibly sets the stored coefficient value therein to zero. It will be seen from the above description that the tap coefficients of the adaptive filter are coupled to only some of the delay elements that are selected by the routing switch 7. Hereinafter, the taps with tap coefficients coupled thereto are called active taps, and those without any coupled tap coefficient are called inactive taps. In the actual tap coefficient adaptive location, tap coefficients which are less in number than the total number of taps are located as initial values at a uniform interval. The taps for which these tap coefficients are located are active taps, and those without any located tap coefficients are inactive taps.
Now, the tap controller 9 will be described. The adaptive filter shown in FIG. 4 may be in either one of two states, i.e., a "first state" and a "second state". State transition is brought about only from the "first state" to the "second state". Whenever the coefficient updating is executed, a maximum coefficient detector 81 receives the coefficient values outputted by the coefficient generators 30.sub.1 to 30.sub.L and the active tap number supplied from a tap number calculator 76, and supplies the active tap number corresponding to the maximum absolute value coefficient. A minimum coefficient detector 71 receives the active tap number from the tap number calculator 76 and the tap coefficients outputted by the coefficient generators, and supplies the active tap number corresponding to the minimum absolute value coefficient through a multiplexer 87 and a distributor 79 to memories 70.sub.1 and 70.sub.2 and also directly to the coefficient clear circuit 77. The coefficient clear circuit 77 outputs the coefficient clear signal to a coefficient generator corresponding to the inputted tap number to clear the corresponding minimum absolute value coefficient to zero. The memories 70.sub.1 and 70.sub.2 store the inputted tap number at the end of a queue and transfers the tap number at the forefront of the queue to a selector 82.
When a predetermined number of coefficient update has been completed times, a counter 86 supplies a control signal to a switch 78 and also to a checking circuit 80. To the switch 78 constants .mu..sub.1 and .mu..sub.2 (.mu..sub.1 &lt;.mu..sub.2) are supplied from a memory 83. The switch 78 is controlled by the counter 86. In its first state, it supplies .mu..sub.1 as step size data to the coefficient generators 30.sub.1 to 30.sub.L. When it is brought to the second state by the control signal from the counter 86, it supplies .mu..sub.2 as the step size data. The controlled tap range calculator 85 receives the tap number data I.sub.max corresponding to the maximum absolute value coefficient supplied from the maximum coefficient detector 81 and calculates (I.sub.max -L) and (I.sub.max +L), which are supplied to the checking circuit 80. The checking circuit 80 checks whether the tap number corresponding to the minimum absolute coefficient supplied from the minimum coefficient detector 71 through the multiplexer 87 is contained in the controlled tap range (I.sub.max .+-.L) supplied from the controlled tap range calculator 85 and generates the control signal. When the control signal supplied from the counter 86 represents the "first state" noted above, however, the checking circuit 80 unconditionally generates the control signal for selecting the memory 70.sub.1. Thus, all the inactive taps have been stored in the memory 70.sub.1 when the coefficient updating is started. The distributor 79 selects either one of the memories 70.sub.1 and 70.sub.2 according to the control signal from the checking circuit 80. Specifically, the distributor 87 selects the memory 70.sub.1 when the tap number supplied from the multiplexer 87 is in the controlled tap range while otherwise selecting the memory 70.sub.2, and transfers the tap number to the selected memory. The memory 70.sub.1 or 70.sub.2 selected by the distributor 79 stores the tap number supplied from the distributor 79.
The memories 70.sub.1 and 70.sub.2 have an FIFO (First-In-First-Out) structure, and cooperate to store (N-L) inactive tap numbers (N being the total number of taps, L being the number of active taps). The tap number calculator 76 calculates the tap number which is obtained by removing the inactive tap numbers stored in the memories 70.sub.1 and 70.sub.2 from the total tap numbers, i.e., the active tap numbers, and supplies these calculated tap numbers as tap switching control signals to the routing switch 7. The routing switch 7 selects the outputs of the delay elements corresponding to the L active tap numbers received from the tap number calculator 76 and transfers the selected outputs to the corresponding coefficient generators. The initial inactive tap numbers, i.e., the initial settings in the memory 70.sub.1, are selected such that the active tap numbers are uniformly spaced apart with respect to the total tap numbers. For example, when the total number of taps is N=13, the number of active taps is L=5, and the number of inactive taps is N-L=8, the total tap numbers are 1, 2, . . . , 13. In this case, the active tap numbers which are stored in the memory 70.sub.1 are initialized as 2, 3, 5, 6, 8, 9, 11 and 12 so that the active tap numbers are uniformly spaced apart as 1, 4, 7, 10 and 13. The inactive tap numbers may be stored in the memory 70.sub.1 in any order; for example, they may be stored in the ascending order, or they may be stored at random. After the above initialization has been completed, the coefficient update of the taps (i.e., active taps) selected by the routing switch 7 is made. Whenever Q (Q being a positive integer) coefficient update have been completed, the locations of the coefficients, i.e., the positions of the active taps, are updated.
In the "first state" noted above, the selector 82 selects the memory 70.sub.1 and discards the tap numbers taken out therefrom. In the "second state", the selector 82 switches, according to a control signal supplied from the controlled tap range calculator 85, two different states, i.e., one in which it selects the memory 70.sub.1 and discards the tap numbers taken out therefrom, and the other one in which it selects either memory 70.sub.1 or 70.sub.2 and supplies the tap numbers taken out therefrom to the multiplexer 87. The controlled tap range calculator 85 judges the variation of Imax supplied from the maximum coefficient detecting circuit 81 and generates the control signal supplied to the selector 82. When a change of I.sub.max is larger than a predetermined threshold value, the selector 82 generates, for a predetermined period of time, a control signal for feeding back tap numbers taken out from the memories 70.sub.1 and 70.sub.2 with alternate switching thereof to the multiplexer 87. When no variation of I.sub.max is detected, the selector 82 generates a control signal for selecting the memory 70.sub.1 and discard the tap numbers taken out therefrom. The variation of Imax can be judged by detecting that Imax is different from the preceding value continuously for a predetermined number of times. The tap numbers supplied from the selector 82 to the multiplexer 87, is fed back by the distributor 79 to the memory 70.sub.1 or 70.sub.2 in accordance with I.sub.max determined by the check circuit 80. In the above procedure, it is possible to shift the inactive tap numbers stored in the memories 70.sub.1 and 70.sub.2 to the other ones thereof when I.sub.max is varied.
It will be seen from the above that in the "first state", in which the coefficient update is completed a predetermined number of times, all the inactive taps are sequentially made effective, and in the subsequent "second state" after the completion only the taps of the tap numbers satisfying (I.sub.max .+-.L) are selectively made effective. According to the tap position control with the limitation of I.sub.max .+-.L, it is possible to realize quick convergence of tap-position control. In the "first state", stable coefficient growth with a small step size is realized, and the maximum coefficient detector 81 determines I.sub.max according to the accurate magnitude relationship of coefficient values obtained at the instant of the state transition to the "second state". Subsequently, the high speed convergence is attained with the usual step size.
In the prior art system as described above, when the input signal has a strong nonstationaricy such as a voice signal, the input signal samples supplied from the delay elements 20.sub.1 to 20.sub.N-1 to the coefficient generators 30.sub.1 to 30.sub.L are greatly different in value. Particularly, the coefficient update in the coefficient generator which receives a smaller input signal sample than those supplied to other coefficient generators, is subject to greater errors, thus leading to erroneous coefficient values and also to erroneous tap control. In addition, when all the computation cannot be completed in one sampling period due to computation capacity restrictions on hardware, it is impossible to realize an adaptive filter with tap position control.